# 37/100 二叉树-二叉树的最大深度
# leetcode第104题: https://leetcode.cn/problems/maximum-depth-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/9
from typing import Optional
from collections import deque
from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test


def maxDepth_dfs(root: Optional[TreeNode]) -> int:
    """我的方法"""

    def dfs(cur: TreeNode, dep):
        if cur:
            if not cur.right and not cur.left:
                res.append(dep)
                return
            if cur.left:
                dfs(cur.left, dep + 1)
            if cur.right:
                dfs(cur.right, dep + 1)

    res = []
    dfs(root, 1)
    return max(res) if res else 0


def maxDepth_levelorder(root: Optional[TreeNode]) -> int:
    # 层序遍历
    if not root:
        return 0
    queue = deque()
    cur = root
    queue.append(cur)
    depth = 0
    while queue:
        size = len(queue)
        for i in range(size):
            cur = queue.popleft()
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)
        depth += 1
    return depth


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([3, 9, 20, None, None, 15, 7])
    t2 = TreeConverter.list_to_tree([1, None, 2])
    t3 = None
    t4 = TreeNode(1)
    t5 = TreeNode(1, None, TreeNode(2, TreeNode(3), None))
    t6 = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5), TreeNode(6, TreeNode(2))))
    inp = [{"root": t1}, {"root": t2}, {"root": t3}, {"root": t4}, {"root": t5}, {"root": t6}]
    out = [3, 2, 0, 1, 3, 4]
    test.test_function(maxDepth_dfs, inp, out)
    test.test_function(maxDepth_levelorder, inp, out)
